[集训队作业2018]-不可名状

推理题推理题？神仙题神仙题！

uoj-bqb3

题意

让你猜一个 $2^n$ 次单位根，$n$ 仅有 $16$，给出四种操作：

  • $INI(n)$: 初始化 $size = 2^n$ 的数组
  • $CU(d, k)$: 下标二进制第 $d$ 位为 $1$ 的乘上 $x^k$
  • $CR(d1, d2, A)$: 下标二进制第 $d1$ 和 $d2$ 位均为 $1$ 的 $i$ 乘上一个 $2 * 2$ 的矩阵
  • $ACR(A)$: $a$ 作为列向量左乘一个 $2^n * 2^n$ 的矩阵
  • $QR()$: 返回 $[0, 2^n)$ 一个整数，返回 $i$ 的概率为 $\frac{|a_i|^2}{\sum_j |a_j|^2}$

推导

假装我们支持：FWT、DFT、IDFT 也就是系数和点值转换

注意到 $QR$ 只能用一次，就不能像量子破碎那样靠期望了。

设 $x = \omega_{2^n}^b$

要让 $QR$ 返回值只有 $b$，必然 $a$ 序列是 $a_i = [i == b]$

这像个系数序列。

考虑什么点值多项式 IDFT 后 $a_i = [i == b]$：$f(x) = x^b$。

点值序列 $a_i = (\omega_{2^n}^b)^i$ 即 $f(x) = x^b$ 在 $\omega_{2^n}^i$ 处的点值，是好构造的，就是二进制拆分 $i$ 为若干 $2^j$ 然后执行若干 $CU(j, 2^j)$（记得在此之前要 FWT 一遍让每个 $a_i = 1$）

整理一下: FWT 让每个 $a_i = 1$，调用若干 $CU(i, 2^i)$ 使得 $a_i = x^i$，IDFT 使得 $a_i = [i == b]$，然后 $QR$ 返回答案。

细节

FWT 是从小到大对每个 $i$ 做 $CR(i, i, M = \{\{1, 1\}, \{1, -1\}\})$（$M$ 还要乘上 $\frac{1}{\sqrt{2}}$。那，DFT/IDFT 又是啥？

考虑模拟 DFT：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void FFT(C *a, int op) {
    rep(i, 0, lim - 1)
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 1; i < lim; i <<= 1) {
        C W(cos(Pi / i), op * sin(Pi / i));
        for (int j = 0; j < lim; j += (i << 1)) {
            C w(1, 0);
            for (int k = 0; k < i; k++, w = w * W) {
                C x = a[j + k], y = w * a[j + k + i];
                a[j + k] = x + y, a[j + k + i] = x - y;
            }
        }
    }
}

这个 FFT 做了什么？

  • 二进制位翻转：把 $CU(i, 2^i)$ 变成 $CU(i, 2^{15 - i})$ 即可
  • 观察它在第 $i$ 层做的事：
    1. 对于第 $i$ 位为 $1$ 的位置 $j$ 乘上了 $\omega_{2^{i + 1}}^{j \mod 2^{i + 1}}$，分解 $j$ 为若干 $2^k$ 和，只有第 $i$、$k$ 位都为 $1$ 的位置才能乘上 $\omega_{2^{i + 1}}^{2^k}$，因此调用 $CR(i, i, \{\{1, 0\}, \{0, \omega_{2^{i + 1}}^{2^k}\}\})$
    2. 就是 FWT 操作，调用 $CR(i, i, M)$

最后虽然有 $(\frac{1}{\sqrt{2}})^n$ 的常数误差但对答案没有影响。

神，量子 yyds！太 nb 了这个题。

好像真的有什么「量子傅里叶逆变换」(quantum phase estimation algorithm)，天！量子计算机？

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include "unnamable.h"
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;
typedef complex<double> C;
C v = 1 / sqrt(2), M[2][2] = {{v, v}, {v, -v}};
C w[16];
void prew() {
  double pi = acos(-1.0);
  rep(i, 0, 15)
    w[i] = C(cos(pi), sin(pi)), pi *= 0.5;
}
C SOL(int t) {
  prew();
  INI(16);
  // FWT
  rep(i, 0, 15) CR(i, i, M);
  // IDFT
  rep(i, 0, 15) CU(i, 1 << (15 - i));
  rep(i, 0, 15) {
    // step 1
    rep(j, 0, i - 1) {
      C dft[2][2];
      dft[0][0] = 1, dft[0][1] = 0;
      dft[1][0] = 0, dft[1][1] = w[i - j];
      CR(i, j, dft);
    }
    // step 2
    CR(i, i, M);
  }
  int ans = 65536 - QR();
  C ret = 1;
  rep(i, 0, 15) if (ans >> i & 1) ret = ret * w[15 - i];
  return ret;
}

吐槽（雾

我真不会玩推理游戏 /px